'''
 计算随机排列 1,2,...,n 中局部极大值的期望个数
'''

import numpy as np
import matplotlib.pyplot as plt
import matplotlib
matplotlib.use(backend="TkAgg")


def count_local_maxima(perm):
    n = len(perm)
    count = 0
    for i in range(1, n-1):
        if perm[i] > perm[i-1] and perm[i] > perm[i+1]:
            count += 1
    return count

def simulate_local_maxima(n, trials=100000):
    counts = []
    for _ in range(trials):
        perm = np.random.permutation(n) + 1  # permutation of 1,...,n
        counts.append(count_local_maxima(perm))
    return np.array(counts)

# 参数
n = 10
trials = 200000
counts = simulate_local_maxima(n, trials)

empirical_mean = counts.mean()
theoretical_mean = (n-2)/3

print(f"n={n}, trials={trials}")
print(f"Empirical mean of local maxima = {empirical_mean:.4f}")
print(f"Theoretical expectation = {theoretical_mean:.4f}")

# 画直方图
plt.figure(figsize=(8,5))
plt.hist(counts, bins=np.arange(counts.min()-0.5, counts.max()+1.5, 1),
         density=True, alpha=0.7, edgecolor='black')
plt.axvline(theoretical_mean, color='red', linestyle='--', linewidth=2, label=f'Theoretical mean = {theoretical_mean:.2f}')
plt.axvline(empirical_mean, color='blue', linestyle=':', linewidth=2, label=f'Empirical mean = {empirical_mean:.2f}')
plt.xlabel("Number of local maxima")
plt.ylabel("Probability")
plt.title(f"Distribution of local maxima count (n={n}, trials={trials})")
plt.legend()
plt.tight_layout()
plt.show()